/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/minimum-path-sum
@Language: C++
@Datetime: 16-02-09 05:12
*/

class Solution {
public:
    /**
     * @param grid: a list of lists of integers.
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    int minPathSum(vector<vector<int> > &grid) {
        // write your code here
        if (grid.size()<1)
            return 0;
        int m = grid.size(),n = grid[0].size();
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                if (i>0 && j>0)
                    grid[i][j]+=(grid[i-1][j]<grid[i][j-1]?grid[i-1][j]:grid[i][j-1]);
                else if(i>0)
                    grid[i][j]+=grid[i-1][j];
                else if (j>0)
                    grid[i][j]+=grid[i][j-1];
        return grid[m-1][n-1];
    }
};
